import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static ArrayList<ArrayList<Character>> levelOrder (MyTree.TreeNode root) {
        // write code here
        Deque<MyTree.TreeNode> deque1=new LinkedList<>();
        Deque<MyTree.TreeNode> deque2=new LinkedList<>();
        ArrayList<ArrayList<Character>> list=new ArrayList<>();

        if(root==null){
            return list;
        }
        deque1.offer(root);
        while(!deque1.isEmpty()||!deque2.isEmpty()){
            ArrayList<Character> list1=new ArrayList<>();
            while(!deque1.isEmpty()){
                while(deque1.peek()==null&&!deque1.isEmpty()){
                    deque1.poll();
                }
                if(deque1.isEmpty()){
                    break;
                }
                deque2.offer(deque1.poll());

            }
            while(!deque2.isEmpty()){

                while(deque2.peek()==null&&!deque2.isEmpty()){
                    deque2.poll();
                }

                MyTree.TreeNode cur=deque2.peek();
                if (cur == null) {
                    break;
                }
                list1.add(cur.val);
                deque1.offer(cur.left);
                deque1.offer(cur.right);
                deque2.poll();
            }

            if(!list1.isEmpty()) {
                list.add(list1);
            }
        }
        return list;

    }

    public static void main(String[] args) {
      MyTree myTree=new MyTree();
      myTree.creatTree1();
        levelOrder(myTree.rootNode);
     

    }
    public static void main1(String[] args) {
        MyTree myTree=new MyTree();
        myTree.rootNode=myTree.creatTree();
        myTree.preOrder(myTree.rootNode);
        System.out.println();
        myTree.inOrder(myTree.rootNode);
        System.out.println();
        myTree.postOrder(myTree.rootNode);
        System.out.println("============");
        List<Character> list1=new ArrayList<>();
        list1=myTree.preorderTraversal(myTree.rootNode);
        System.out.println(list1);
    }

}
